27.3 KB · ⇊ 16 parts · ⤓ Micron 27.3 KB · ⤓ HTML 167.0 KB

top

In mathematics, an extreme point of a convex set S {\displaystyle S} in a real or complex vector space is a point in S {\displaystyle S} that does not lie in any open line segment joining two points of S . {\displaystyle S.} The extreme points of a line segment are called its endpoints. In linear programming problems, an extreme point is also called vertex or corner point of S . {\displaystyle S.} cite-ref-1[1]

• Definition

• Characterizations

• Examples

• Properties

• Theorems

• Krein–Milman theorem

• For Banach spaces

• Related notions

• k -extreme points

• See also

• Citations

• Bibliography

Throughout, it is assumed that X {\displaystyle X} is a real or complex vector space.

For any p , x , y ∈ ∈ X , {\displaystyle p,x,y\in X,} say that p {\displaystyle p} lies betweencite-ref-footnotenaricibeckenstein2011275-339-2-0[2] x {\displaystyle x} and y {\displaystyle y} if x ≠ ≠ y {\displaystyle x\neq y} and there exists a 0 < t < 1 {\displaystyle 0<t<1} such that p = t x + ( 1 − − t ) y . {\displaystyle p=tx+(1-t)y.}

If K {\displaystyle K} is a subset of X {\displaystyle X} and p ∈ ∈ K , {\displaystyle p\in K,} then p {\displaystyle p} is called an extreme pointcite-ref-footnotenaricibeckenstein2011275-339-2-1[2] of K {\displaystyle K} if it does not lie between any two distinct points of K . {\displaystyle K.} That is, if there does not exist x , y ∈ ∈ K {\displaystyle x,y\in K} and 0 < t < 1 {\displaystyle 0<t<1} such that x ≠ ≠ y {\displaystyle x\neq y} and p = t x + ( 1 − − t ) y . {\displaystyle p=tx+(1-t)y.} The set of all extreme points of K {\displaystyle K} is denoted by extreme ⁡ ⁡ ( K ) . {\displaystyle \operatorname {extreme} (K).}

If S {\displaystyle S} is a subset of a vector space then a linear sub-variety (that is, an affine subspace) A {\displaystyle A} of the vector space is called a support variety if A {\displaystyle A} meets S {\displaystyle S} (that is, A ∩ ∩ S {\displaystyle A\cap S} is not empty) and every open segment I ⊆ ⊆ S {\displaystyle I\subseteq S} whose interior meets A {\displaystyle A} is necessarily a subset of A . {\displaystyle A.} cite-ref-footnotegrothendieck1973186-3-0[3] A 0-dimensional support variety is called an extreme point of S . {\displaystyle S.} cite-ref-footnotegrothendieck1973186-3-1[3]

The midpointcite-ref-footnotenaricibeckenstein2011275-339-2-2[2] of two elements x {\displaystyle x} and y {\displaystyle y} in a vector space is the vector 1 2 ( x + y ) . {\displaystyle {\tfrac {1}{2}}(x+y).}

For any elements x {\displaystyle x} and y {\displaystyle y} in a vector space, the set [ x , y ] = { t x + ( 1 − − t ) y : 0 ≤ ≤ t ≤ ≤ 1 } {\displaystyle [x,y]=\{tx+(1-t)y:0\leq t\leq 1\}} is called the closed line segment or closed interval between x {\displaystyle x} and y . {\displaystyle y.} The open line segment or open interval between x {\displaystyle x} and y {\displaystyle y} is ( x , x ) = ∅ ∅ {\displaystyle (x,x)=\varnothing } when x = y {\displaystyle x=y} while it is ( x , y ) = { t x + ( 1 − − t ) y : 0 < t < 1 } {\displaystyle (x,y)=\{tx+(1-t)y:0<t<1\}} when x ≠ ≠ y . {\displaystyle x\neq y.} cite-ref-footnotenaricibeckenstein2011275-339-2-3[2] The points x {\displaystyle x} and y {\displaystyle y} are called the endpoints of these interval. An interval is said to be a non−degenerate interval or a proper interval if its endpoints are distinct. The midpoint of an interval is the midpoint of its endpoints.

The closed interval [ x , y ] {\displaystyle [x,y]} is equal to the convex hull of ( x , y ) {\displaystyle (x,y)} if (and only if) x ≠ ≠ y . {\displaystyle x\neq y.} So if K {\displaystyle K} is convex and x , y ∈ ∈ K , {\displaystyle x,y\in K,} then [ x , y ] ⊆ ⊆ K . {\displaystyle [x,y]\subseteq K.}

If K {\displaystyle K} is a nonempty subset of X {\displaystyle X} and F {\displaystyle F} is a nonempty subset of K , {\displaystyle K,} then F {\displaystyle F} is called a facecite-ref-footnotenaricibeckenstein2011275-339-2-4[2] of K {\displaystyle K} if whenever a point p ∈ ∈ F {\displaystyle p\in F} lies between two points of K , {\displaystyle K,} then those two points necessarily belong to F . {\displaystyle F.}

Theoremcite-ref-footnotenaricibeckenstein2011275-339-2-5[2]—Let K {\displaystyle K} be a non-empty convex subset of a vector space X {\displaystyle X} and let p ∈ ∈ K . {\displaystyle p\in K.} Then the following statements are equivalent:

1. p {\displaystyle p} is an extreme point of K . {\displaystyle K.}

2. K ∖ ∖ { p } {\displaystyle K\setminus \{p\}} is convex.

3. p {\displaystyle p} is not the midpoint of a non-degenerate line segment contained in K . {\displaystyle K.}

4. for any x , y ∈ ∈ K , {\displaystyle x,y\in K,} if p ∈ ∈ [ x , y ] {\displaystyle p\in [x,y]} then x = p or y = p . {\displaystyle x=p{\text{ or }}y=p.}

5. if x ∈ ∈ X {\displaystyle x\in X} is such that both p + x {\displaystyle p+x} and p − − x {\displaystyle p-x} belong to K , {\displaystyle K,} then x = 0. {\displaystyle x=0.}

6. { p } {\displaystyle \{p\}} is a face of K . {\displaystyle K.}

If a < b {\displaystyle a<b} are two real numbers then a {\displaystyle a} and b {\displaystyle b} are extreme points of the interval [ a , b ] . {\displaystyle [a,b].} However, the open interval ( a , b ) {\displaystyle (a,b)} has no extreme points.cite-ref-footnotenaricibeckenstein2011275-339-2-6[2] Any open interval in R {\displaystyle \mathbb {R} } has no extreme points while any non-degenerate closed interval not equal to R {\displaystyle \mathbb {R} } does have extreme points (that is, the closed interval's endpoint(s)). More generally, any open subset of finite-dimensional Euclidean space R n {\displaystyle \mathbb {R} ^{n}} has no extreme points.

The extreme points of the closed unit disk in R 2 {\displaystyle \mathbb {R} ^{2}} is the unit circle.

The perimeter of any convex polygon in the plane is a face of that polygon.cite-ref-footnotenaricibeckenstein2011275-339-2-7[2] The vertices of any convex polygon in the plane R 2 {\displaystyle \mathbb {R} ^{2}} are the extreme points of that polygon.

An injective linear map F : X → → Y {\displaystyle F:X\to Y} sends the extreme points of a convex set C ⊆ ⊆ X {\displaystyle C\subseteq X} to the extreme points of the convex set F ( X ) . {\displaystyle F(X).} cite-ref-footnotenaricibeckenstein2011275-339-2-8[2] This is also true for injective affine maps.

The extreme points of a compact convex set form a Baire space (with the subspace topology) but this set may fail to be closed in X . {\displaystyle X.} cite-ref-footnotenaricibeckenstein2011275-339-2-9[2]

The Krein–Milman theorem is arguably one of the most well-known theorems about extreme points.

Krein–Milman theorem—If S {\displaystyle S} is convex and compact in a locally convex topological vector space, then S {\displaystyle S} is the closed convex hull of its extreme points: In particular, such a set has extreme points.

These theorems are for Banach spaces with the Radon–Nikodym property.

A theorem of Joram Lindenstrauss states that, in a Banach space with the Radon–Nikodym property, a nonempty closed and bounded set has an extreme point. (In infinite-dimensional spaces, the property of compactness is stronger than the joint properties of being closed and being bounded.cite-ref-artstein1980-4-0[4])

Theorem (Gerald Edgar)—Let E {\displaystyle E} be a Banach space with the Radon–Nikodym property, let C {\displaystyle C} be a separable, closed, bounded, convex subset of E , {\displaystyle E,} and let a {\displaystyle a} be a point in C . {\displaystyle C.} Then there is a probability measure p {\displaystyle p} on the universally measurable sets in C {\displaystyle C} such that a {\displaystyle a} is the barycenter of p , {\displaystyle p,} and the set of extreme points of C {\displaystyle C} has p {\displaystyle p} -measure 1.cite-ref-5[5]

Edgar’s theorem implies Lindenstrauss’s theorem.

A closed convex subset of a topological vector space is called strictly convex if every one of its (topological) boundary points is an extreme point.cite-ref-footnotehalmos19825-6-0[6] The unit ball of any Hilbert space is a strictly convex set.cite-ref-footnotehalmos19825-6-1[6]

More generally, a point in a convex set S {\displaystyle S} is k {\displaystyle k} -extreme if it lies in the interior of a k {\displaystyle k} -dimensional convex set within S , {\displaystyle S,} but not a k + 1 {\displaystyle k+1} -dimensional convex set within S . {\displaystyle S.} Thus, an extreme point is also a 0 {\displaystyle 0} -extreme point. If S {\displaystyle S} is a polytope, then the k {\displaystyle k} -extreme points are exactly the interior points of the k {\displaystyle k} -dimensional faces of S . {\displaystyle S.} More generally, for any convex set S , {\displaystyle S,} the k {\displaystyle k} -extreme points are partitioned into k {\displaystyle k} -dimensional open faces.

The finite-dimensional Krein–Milman theorem, which is due to Minkowski, can be quickly proved using the concept of k {\displaystyle k} -extreme points. If S {\displaystyle S} is closed, bounded, and n {\displaystyle n} -dimensional, and if p {\displaystyle p} is a point in S , {\displaystyle S,} then p {\displaystyle p} is k {\displaystyle k} -extreme for some k ≤ ≤ n . {\displaystyle k\leq n.} The theorem asserts that p {\displaystyle p} is a convex combination of extreme points. If k = 0 {\displaystyle k=0} then it is immediate. Otherwise p {\displaystyle p} lies on a line segment in S {\displaystyle S} which can be maximally extended (because S {\displaystyle S} is closed and bounded). If the endpoints of the segment are q {\displaystyle q} and r , {\displaystyle r,} then their extreme rank must be less than that of p , {\displaystyle p,} and the theorem follows by induction.

• Extreme set

• Exposed point

• Choquet theory – Area of functional analysis and convex analysis

• Bang–bang controlcite-ref-artstein1980-4-1[4]

cite-note-11. ↑ citerefsaltzmanSaltzman, Matthew. "What is the difference between corner points and extreme points in linear programming problems?".

cite-note-footnotenaricibeckenstein2011275-339-22. ↑ Narici & Beckenstein 2011, pp. 275–339.

cite-note-footnotegrothendieck1973186-33. ↑ Grothendieck 1973, p. 186.

cite-note-artstein1980-44. ↑ citerefartstein1980Artstein, Zvi (1980). "Discrete and continuous bang-bang and facial spaces, or: Look for the extreme points". SIAM Review. 22 (2): 172–185. doi:10.1137/1022026. JSTOR 2029960. MR 0564562.

cite-note-55. ↑ Edgar GA. A noncompact Choquet theorem. Proceedings of the American Mathematical Society. 1975;49(2):354–8.

cite-note-footnotehalmos19825-66. ↑ Halmos 1982, p. 5.

• citerefadaschernstkeim1978Adasch, Norbert; Ernst, Bruno; Keim, Dieter (1978). Topological Vector Spaces: The Theory Without Convexity Conditions. Lecture Notes in Mathematics. Vol. 639. Berlin New York: Springer-Verlag. ISBN 978-3-540-08662-8. OCLC 297140003.

• citerefbourbaki1987Bourbaki, Nicolas (1987) [1981]. Topological Vector Spaces: Chapters 1–5. Éléments de mathématique. Translated by Eggleston, H.G.; Madan, S. Berlin New York: Springer-Verlag. ISBN 3-540-13627-4. OCLC 17499190.

• citerefpaul-e-black2004Paul E. Black, ed. (2004-12-17). "extreme point". Dictionary of algorithms and data structures. US National institute of standards and technology. Retrieved 2011-03-24.

• citerefborowskiborwein1989Borowski, Ephraim J.; Borwein, Jonathan M. (1989). "extreme point". Dictionary of mathematics. Collins dictionary. HarperCollins. ISBN 0-00-434347-6.

• citerefgrothendieck1973Grothendieck, Alexander (1973). Topological Vector Spaces. Translated by Chaljub, Orlando. New York: Gordon and Breach Science Publishers. ISBN 978-0-677-30020-7. OCLC 886098.

• citerefhalmos1982Halmos, Paul R. (8 November 1982). A Hilbert Space Problem Book. Graduate Texts in Mathematics. Vol. 19 (2nd ed.). New York: Springer-Verlag. ISBN 978-0-387-90685-0. OCLC 8169781.

• citerefjarchow1981Jarchow, Hans (1981). Locally convex spaces. Stuttgart: B.G. Teubner. ISBN 978-3-519-02224-4. OCLC 8210342.

• citerefk-the1983Köthe, Gottfried (1983) [1969]. Topological Vector Spaces I. Grundlehren der mathematischen Wissenschaften. Vol. 159. Translated by Garling, D.J.H. New York: Springer Science & Business Media. ISBN 978-3-642-64988-2. MR 0248498. OCLC 840293704.

• citerefk-the1979Köthe, Gottfried (1979). Topological Vector Spaces II. Grundlehren der mathematischen Wissenschaften. Vol. 237. New York: Springer Science & Business Media. ISBN 978-0-387-90400-9. OCLC 180577972.

• citerefnaricibeckenstein2011Narici, Lawrence; Beckenstein, Edward (2011). Topological Vector Spaces. Pure and applied mathematics (Second ed.). Boca Raton, FL: CRC Press. ISBN 978-1584888666. OCLC 144216834.

• citerefrobertsonrobertson1980Robertson, Alex P.; Robertson, Wendy J. (1980). Topological Vector Spaces. Cambridge Tracts in Mathematics. Vol. 53. Cambridge England: Cambridge University Press. ISBN 978-0-521-29882-7. OCLC 589250.

• citerefrudin1991Rudin, Walter (1991). Functional Analysis. International Series in Pure and Applied Mathematics. Vol. 8 (Second ed.). New York, NY: McGraw-Hill Science/Engineering/Math. ISBN 978-0-07-054236-5. OCLC 21163277.

• citerefschaeferwolff1999Schaefer, Helmut H.; Wolff, Manfred P. (1999). Topological Vector Spaces. GTM. Vol. 8 (Second ed.). New York, NY: Springer New York Imprint Springer. ISBN 978-1-4612-7155-0. OCLC 840278135.

• citerefschechter1996Schechter, Eric (1996). Handbook of Analysis and Its Foundations. San Diego, CA: Academic Press. ISBN 978-0-12-622760-4. OCLC 175294365.

• citereftr-ves2006Trèves, François (2006) [1967]. Topological Vector Spaces, Distributions and Kernels. Mineola, N.Y.: Dover Publications. ISBN 978-0-486-45352-1. OCLC 853623322.

• citerefwilansky2013Wilansky, Albert (2013). Modern Methods in Topological Vector Spaces. Mineola, New York: Dover Publications, Inc. ISBN 978-0-486-49353-4. OCLC 849801114.